251. Flatten 2D Vector
Medium

Design an iterator to flatten a 2D vector. It should support the next and hasNext operations.

Implement the Vector2D class:

  • Vector2D(int[][] vec) initializes the object with the 2D vector vec.
  • next() returns the next element from the 2D vector and moves the pointer one step forward. You may assume that all the calls to next are valid.
  • hasNext() returns true if there are still some elements in the vector, and false otherwise.

 

Example 1:

Input
["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"]
[[[[1, 2], [3], [4]]], [], [], [], [], [], [], []]
Output
[null, 1, 2, 3, true, true, 4, false]

Explanation
Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]);
vector2D.next();    // return 1
vector2D.next();    // return 2
vector2D.next();    // return 3
vector2D.hasNext(); // return True
vector2D.hasNext(); // return True
vector2D.next();    // return 4
vector2D.hasNext(); // return False

 

Constraints:

  • 0 <= vec.length <= 200
  • 0 <= vec[i].length <= 500
  • -500 <= vec[i][j] <= 500
  • At most 105 calls will be made to next and hasNext.

 

Follow up: As an added challenge, try to code it using only iterators in C++ or iterators in Java.

Accepted
89,791
Submissions
192,381
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
How many variables do you need to keep track?
Show Hint 2
Two variables is all you need. Try with x and y.
Show Hint 3
Beware of empty rows. It could be the first few rows.
Show Hint 4
To write correct code, think about the invariant to maintain. What is it?
Show Hint 5
The invariant is x and y must always point to a valid point in the 2d vector. Should you maintain your invariant ahead of time or right when you need it?
Show Hint 6
Not sure? Think about how you would implement hasNext(). Which is more complex?
Show Hint 7
Common logic in two different places should be refactored into a common method.

Average Rating: 4.75 (28 votes)

Premium

Solution


Overview

This question should be fairly straightforward if you're familiar with what an Iterator is. If you aren't at all familiar with Iterators though, then we suggest having a go at Peeking Iterator. Additionally, the Solution Article for Peeking Iterator has a special introduction section that introduces you to what Iterators are.

Note that this question refers to something called a Vector. A Vector is simply another name for Array. To be consistent with the question, we've chosen to use the term Vector, rather than Array for this article (Sorry in advance for any confusion this causes, C++ programmers).



Approach 1: Flatten List in Constructor

Intuition

This approach is a bad approach! We've included it though, to show what it looks like, and to discuss why it's bad. This will help you to design good Iterators.

In the constructor, we can iterate over the 2D input vector, putting each integer into a List. Then, the problem simplifies to being a simple List Iterator. Note that the reason we use a List rather than an array (vector) is because we don't know in advance how many integers there might be in total.

Our unpack algorithm would be as follows.

nums = a new List
for each innerVector in the input 2D Vector:
    for each number in innerVector:
        append number to the end of nums

We'll then need to save this List as a field of our Iterator class, seeing as the next(...) and hasNext(...) methods will need to access it repeatedly. By then also having a position field, we can keep track of where the Iterator is up to.

Algorithm

The code shown here makes the position field point at the next element that needs to be returned by next. Therefore, the hasNext() method simply needs to check that position is a valid index of nums. A similar variant would be to make position point at the previous value that was returned. This would simplify the next() method, but complicate the hasNext() method.

Complexity Analysis

Let NN be the number of integers within the 2D Vector, and VV be the number of inner vectors.

  • Time complexity.

    • Constructor: O(N+V)O(N + V).

      In total, we'll append NN integers to the nums list. Each of these appends is an O(1)O(1) operation. This gives us O(N)O(N).

      Something to be cautious of is that inner vectors don't have to contain integers. Think of a test cases such as [[], [2], [], [], []]. For this test case, N=1N = 1, because there's only one integer within it. However, the algorithm has to loop through all of the empty vectors. The cost of checking all the vectors is O(V)O(V).

      Therefore, we get a final time complexity of O(N+V)O(N + V).

    • next(): O(1)O(1).

      All operations in this method, including getting the integer at a specific index of a list, are O(1)O(1).

    • hasNext(): O(1)O(1).

      All operations in this method are O(1)O(1).

  • Space complexity : O(N)O(N).

    We're making a new list that contains all of the integers from the 2D Vector. Notice that this is different from the time complexity; in the example of [[], [2], [], [], []], we only store the 2. All information about how many inner vectors there were is discarded.

Why is this implementation bad?

This code works, it runs fast here on Leetcode, it seems pretty straightforward to implement.

However, one of the main purposes of an Iterator is to minimize the use of auxiliary space. We should try to utilize the existing data structure as much as possible, only adding as much extra space as needed to keep track of the next value. In some situations, the data structure we want to iterate over is too large to even fit in memory anyway (think of file systems).

In the case of our above implementation, we might as well have just had a single function List<Integer> getFlattenedVector(int[][] v), which would return a List of integers, that could then be iterated over using the List types own standard Iterator.

As a general rule, you should be very cautious of implementing Iterators with a high time complexity in the constructor, with a very low time complexity in the next() and hasNext() methods. If the code using the Iterator only wanted to access the first couple of elements in the iterated collection, then a lot of time (and probably space) has been wasted!

As a side note, modifying the input collection in any way is bad design too. Iterators are only allowed to look at, not change, the collection they've been asked to iterate over.



Approach 2: Two Pointers

Intuition

Like we said above, Approach 1 is bad because it creates a new data structure instead of simply iterating over the given one. Instead, we should find a way to step through the integers one-by-one, keeping track of where we currently are in the 2D vector. The location of each number is represented with 2 indexes; the index of the inner vector, and the index of the integer within its inner vector. Here's an example 2D vector, with the indexes marked on it.

Diagram showing list with outer and inner indices

Suppose we are at the following position:

Diagram showing list item with it's inner and outer index

How do we find the next position? Well the current integer has another integer after it, within the same inner vector. Therefore, we can just increment inner index by 1. This gives the next position as shown below.

Diagram showing list item advanced to sibling

Now inner is at the end of the current inner vector. In order to get to the next integer we'll need to increment outer by 1, and set inner to 0 (as 0 is first index of the new vector).

Diagram showing list item advanced to first element of next inner vector

This time, it's a bit trickier, because we need to skip over empty vectors. To do that we repeatedly increment outer until we find an inner vector that is not empty (programmatically, this would be an outer where inner = 0 is valid). Once we find one, we stop and set inner to 0 (the first integer of the inner vector).

Diagram showing list item advanced past empty lists to next position

Note that when outer becomes equal to the length of the 2D vector, this means there are no more inner vectors and so there are no more numbers left.

Algorithm

In Approach 1, we used O(N)O(N) auxiliary space and O(N+V)O(N + V) time in the constructor. In this approach though, we perform the necessary work incrementally during calls to hasNext() and next(). This means that if the caller stops using the iterator before it's exhausted, we won't have done any unnecessary work.

We'll define an advanceToNext() helper method that checks if the current inner and outer values point to an integer, and if they don't, then it moves them forward until they point to an integer (in the way described above). If outer == vector.length becomes true, then the method terminates (because there's no integers left).

In order to ensure no unnecessary work is done, the constructor doesn't check whether or not vector[0][0] points to an integer. This is because there might be an arbitrary number of empty inner vectors at the start of the input vector; potentially costing up to O(V)O(V) operations to skip past.

Both hasNext() and next() start by calling advanceToNext() to ensure that inner and outer point to an integer, or that outer is at its "stop" value of outer = vector.length.

next() returns the integer at vector[inner][outer], and then increments inner by 1, so that the next call to advanceToNext() will start searching from after the integer we've just returned.

It is important to note that calling the hasNext() method will only cause the pointers to move if they don't point to an integer. Once they point to an integer, repeated calls to hasNext() will not move them further. Only next() is able to move them off a valid integer. This design ensures that the client code calling hasNext() multiple times will not have unusual side effects.

Complexity Analysis

Let NN be the number of integers within the 2D Vector, and VV be the number of inner vectors.

  • Time complexity.

    • Constructor: O(1)O(1).

      We're only storing a reference to the input vector—an O(1)O(1) operation.

    • advanceToNext(): O(VN)O(\dfrac{V}{N}).

      If the iterator is completely exhausted, then all calls to advanceToNext() will have performed O(N+V)O(N + V) total operations. (Like in Approach 1, the VV comes from the fact that we go through all VV inner vectors, and the NN comes from the fact we perform one increment for each integer).

      However, because we perform NN advanceToNext() operations in order to exhaust the iterator, the amortized cost of this operation is just O(N+V)N=O(NN+VN)=O(VN)\dfrac{O(N + V)}{N} = O(\dfrac{N}{N} + \dfrac{V}{N}) = O(\dfrac{V}{N}).

    • next() / hasNext(): O(VN)O(\dfrac{V}{N}) or O(1)O(1).

      The cost of both these methods depends on how they are called. If we just got a value from next(), then the next call to either method will involve calling advanceToNext(). In this case the time complexity is O(VN)O(\dfrac{V}{N}).

      However if we call hasNext(), then all successive calls to hasNext(), or the next call to next(), will be O(1)O(1). This is because advanceToNext() will only perform an O(1)O(1) check and immediately return.

  • Space complexity : O(1)O(1).

    We only use a fixed set of O(1)O(1) fields (remember vector is a reference, not a copy!). So the space complexity is O(1)O(1).


Report Article Issue

Comments: 11
xidada's avatar
Read More

just wondering why [[[]]] is a valid input for initialization in the testing cases...

40
Show 1 reply
Reply
Share
Report
migeater's avatar
Read More

This solution ignore "follow up".

8
Reply
Share
Report
bshaibu's avatar
Read More

Nice article! There's a really good amount of detail added even for explaining why the invalid solution is not the right approach for an iterator. The complexity analysis was pretty useful, especially for the flatten constructor and the 2 pointer's advanceToNext.

I think there's a small bug in the Python code for the cheat/flatten list solution on line 6

        for (int[] innerVector : v) {

maybe a leftover from translating Java to Python?

5
Reply
Share
Report
cindy0092's avatar
Read More

Problem with the 2nd approach implementation is if you don't ensure the content of [i,j] [0,0] is valid in the constructor, then the first next() call will be invalid.

2
Reply
Share
Report
bc12345's avatar
Read More

Can someone explain the time complexity of the 2nd solution? I still don't get why it's O(V/N)

1
Reply
Share
Report
ausafahmed's avatar
Read More

Nice article, but wondering why use inner == vector[outer].length in the while loop of the second approach?

1
Show 2 replies
Reply
Share
Report
infoparadox9's avatar
Read More

Very well explained! Thanks a lot @Hai_dee

1
Reply
Share
Report
Coba's avatar
Read More

Advance_To_Next is unbelievably over-complicated and convoluted. Why would you introduce some unnecessary engineering? Why can't it be called advance_to_next_row?

0
Reply
Share
Report
DJSagarAhire's avatar
Read More

In Approach 2:

next() returns the integer at vector[inner][outer]

Shouldn't it be vector[outer][inner]?

0
Reply
Share
Report
semi_martingale's avatar
Read More

It's amortized O(1) anyway since V<=N, isn't it?

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.